class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        //1.创建dp表
        int[][] dp = new int[m+1][n+1];

        //2.初始化
        for(int i = 0; i < m+1; i++) dp[i][0] = Integer.MAX_VALUE;
        for(int j = 2; j < n+1; j++) dp[0][j] = Integer.MAX_VALUE;
        dp[0][1] = 0;

        //3.填表
        for(int i = 1; i < m+1; i++) {
            for(int j = 1; j < n+1; j++) {
                if(Math.abs(dp[i-1][j] + dungeon[i-1][j-1]) <= Math.abs(dp[i][j-1] + dungeon[i-1][j-1])) {
                    dp[i][j] = dp[i-1][j] + dungeon[i-1][j-1];
                }else {
                    dp[i][j] = dp[i][j-1] + dungeon[i-1][j-1];
                }
                // if(dungeon[i-1][j-1] >= 0) {
                //     dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]);
                //     sum += dungeon[i-1][j-1];
                // }else {
                //     dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) - dungeon[i-1][j-1] - sum;
                //     sum = 0;
                // }
            }
        }

        //4.返回值
        return dp[m][n];
    }
}